{"cells":[{"cell_type":"markdown","metadata":{"id":"11n5gndbRzoY"},"source":["# Algorithms\n"]},{"cell_type":"markdown","metadata":{"id":"AIFsv_RZ1iV0"},"source":["\n"," \n"," \n","
\n"," \"Open\n"," \n"," \n","
"]},{"cell_type":"markdown","metadata":{},"source":["Programming = Algorithm + Data structure!"]},{"cell_type":"markdown","metadata":{"id":"joZvVURYALD3"},"source":["### A taste of algorithm"]},{"cell_type":"markdown","metadata":{"id":"wJjIP5Vne7cM"},"source":["An informal definition of an algorithm is:\n","\n","> Algorithm: a step-by-step method for solving a problem or doing a task. It is a recipe for the program!\n","\n","In this definition, an algorithm is independent of the computer system. More specifically, we should also note that the algorithm accepts input data and creates output data \n","\n","
\n","\n","\n","Let us elaborate on this simple definition with an example. We want to develop an algorithm for **finding the largest integer among a list of positive integers.** It is obvious that finding the largest integer among many integers is a task that cannot be done in one step. The algorithm needs to test each integer one by one. \n","\n","To solve this problem, we need an intuitive approach. First use a small number of integers (for example, five), then extend the solution to any number of integers. Assume that the algorithm handles the integers one by one. It looks at the first integer without knowing the values of the remaining integers. After it handles the first one, it looks at the second integer, and so on.\n","\n","
"]},{"cell_type":"markdown","metadata":{"id":"Ov2zGQZ0fpWN"},"source":["The above figure does not show what should be done in each step. We can modify the figure to show more details."]},{"cell_type":"markdown","metadata":{"id":"ysPAJS9jnuXm"},"source":["
\n","\n","\n"]},{"cell_type":"markdown","metadata":{"id":"LdvzSD5df2aj"},"source":["There are two problems for the above figure to become an algorithm that can be programmed. First, the **action** in the first step is different than those for the other steps. Second, the wording is not the same in steps 2 to 5. The \n","reason that the first step is different than the other steps is because Largest is not initialized! If we initialize Largest to $-∞$, then the first step can be the same as the other steps!"]},{"cell_type":"markdown","metadata":{"id":"q6YVeAxAn3hM"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"GLxjoqHU_q-Q"},"source":["Is it possible to generalize the algorithm? We want to find the largest of `n` positive integers, where `n` can be 1000, 1000000, or more. We can tell the computer to repeat the steps `n` times!"]},{"cell_type":"markdown","metadata":{"id":"pvz16w-wnJox"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"Fa3TlCNnARdG"},"source":["### Algorithm representations"]},{"cell_type":"markdown","metadata":{"id":"HMP6cPz0Abm9"},"source":["Computer scientists have defined three constructs for a structured program or algorithm. The idea is that a program must be made of a combination of only these three constructs: **sequence, decision, and repetition**. You can use either UML diagram or pseudo code as the recipe (algorithm representation). \n","\n","> It has been proven there is no need for any other constructs!"]},{"cell_type":"markdown","metadata":{"id":"4sSXLtA6BUrk"},"source":["
"]},{"cell_type":"code","execution_count":1,"metadata":{"id":"DWuaau4TCIqU"},"outputs":[{"name":"stdout","output_type":"stream","text":["x is even\n"]}],"source":["x = 150\n","if x%2 == 0:\n"," print('x is even')\n","else:\n"," print('x is odd')"]},{"cell_type":"code","execution_count":2,"metadata":{"id":"0hcb0stsCd_U"},"outputs":[{"name":"stdout","output_type":"stream","text":["0\n","1\n","2\n","3\n","4\n","5\n","6\n","7\n","8\n","9\n"]}],"source":["n = 0\n","while (n < 10):\n"," print(n)\n"," n = n + 1"]},{"cell_type":"markdown","metadata":{"id":"JbujD3GoCnTk"},"source":["> #### Example 1: Write an algorithm that finds the sum of two integers."]},{"cell_type":"markdown","metadata":{"id":"I3Rm1v9OC5Ez"},"source":["This is a simple problem that can be solved using only the sequence construct. Note also that we name the algorithm, define the input to the algorithm and, at the end, we use a `return` instruction to return the sum\n","\n","
"]},{"cell_type":"code","execution_count":3,"metadata":{"id":"PvWULaYcC_rj"},"outputs":[],"source":["def SumOfTwo(first, second):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," first: int\n"," The first integer\n"," second: int\n"," The second integer\n"," Returns\n"," -------\n"," sum : int\n"," The sum of two integers\n"," \"\"\"\n"," # Your code here\n"," sum = first + second\n"," return sum"]},{"cell_type":"code","execution_count":4,"metadata":{"id":"o67HJ2v0DZVT"},"outputs":[],"source":["assert(SumOfTwo(3,5)==8)\n","assert(SumOfTwo(-7,-3)==-10)"]},{"cell_type":"markdown","metadata":{"id":"5Bzy4EE-Dqn6"},"source":["> #### Example 2: Write an algorithm to change a numeric grade to a pass/no pass grade."]},{"cell_type":"markdown","metadata":{"id":"UAGsHKnzDvmK"},"source":["This problem cannot be solved with only the sequence construct. We also need the decision construct. The computer is given an integer between 0 and 100. It returns ‘pass’ if the integer is greater than or equal to 70, and returns ‘nopass’ if the integer is less than 70.\n","\n","
"]},{"cell_type":"code","execution_count":5,"metadata":{"id":"lt-ZqXI3D5ZU"},"outputs":[],"source":["def Pass_NoPass(score):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," score: int\n"," The score to be changed to grade\n"," Returns\n"," -------\n"," grade : str\n"," The grade\n"," \"\"\"\n"," # Your code here\n"," if score >= 70:\n"," grade = \"pass\"\n"," else:\n"," grade = \"nopass\"\n"," return grade"]},{"cell_type":"code","execution_count":6,"metadata":{"id":"TspL7Db8EYWU"},"outputs":[],"source":["assert(Pass_NoPass(90)==\"pass\")\n","assert(Pass_NoPass(55)==\"nopass\")"]},{"cell_type":"markdown","metadata":{"id":"84czTNd4EzMT"},"source":["> #### Example 3: Write an algorithm to find the largest of a set of integers. We do not know the number of integers. Return negative infinity if the input is an empty list."]},{"cell_type":"markdown","metadata":{"id":"HtPxMhL1E3lK"},"source":["We use the concept before to write an algorithm for this problem\n","\n","
"]},{"cell_type":"code","execution_count":7,"metadata":{"id":"Hxai6NkrFPga"},"outputs":[],"source":["import math\n","\n","def FindLargest(ilist):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," ilist: list\n"," The input list that contains integers\n"," Returns\n"," -------\n"," largest : int\n"," The largest integer\n"," \"\"\"\n"," # Your code here\n"," largest = - math.inf\n"," for current in ilist:\n"," if current > largest:\n"," largest = current\n"," else:\n"," pass\n"," return largest"]},{"cell_type":"code","execution_count":8,"metadata":{"id":"dGvVVmSvGVAS"},"outputs":[],"source":["assert(FindLargest([])==-math.inf)\n","assert(FindLargest([7,3,5,10])==10)\n","assert(FindLargest([-7,-2,5,18])==18)"]},{"cell_type":"markdown","metadata":{"id":"Z7GL-urUGw-Y"},"source":["> #### Exercise 1: Write an algorithm to find the smallest among the first 5 integers in a set of integers. Return infinity if the input is an empty list."]},{"cell_type":"markdown","metadata":{"id":"4nWbW8KNG9no"},"source":["Here we need a counter to count the number of integers."]},{"cell_type":"code","execution_count":9,"metadata":{"id":"ylsvYaztHEd5"},"outputs":[],"source":["def FindSmallest(ilist):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," ilist: list\n"," The input list that contains integers\n"," Returns\n"," -------\n"," largest : int\n"," The smallest integer of the first 5 integers in the list\n"," \"\"\"\n"," # Your code here\n"," smallest = math.inf\n"," if len(ilist) != 0:\n"," counter = 0\n"," while(counter<5):\n"," if ilist[counter] < smallest:\n"," smallest = ilist[counter]\n"," counter = counter +1\n"," return smallest"]},{"cell_type":"code","execution_count":10,"metadata":{"id":"aInoO3A3IJZY"},"outputs":[],"source":["assert(FindSmallest([])== math.inf)\n","assert(FindSmallest([7,3,5,10,6])==3)\n","assert(FindSmallest([7,4,5,10,6,1])==4)"]},{"cell_type":"markdown","metadata":{"id":"UMo588t4rY-O"},"source":["## A more formal definition"]},{"cell_type":"markdown","metadata":{"id":"3cbVny0qrb2X"},"source":["Now that we have discussed the concept of an algorithm and shown its representation, here is a more formal definition.\n","\n","> Algorithm: An ordered set of unambiguous steps that produces a result and terminates in a finite time."]},{"cell_type":"markdown","metadata":{"id":"ZBmWzbZrrodF"},"source":["1. **Well-Defined**: An algorithm must be a well-defined, ordered set of instructions.\n","2. **Unambiguous steps**: Each step in an algorithm must be clearly and unambiguously defined. If one step is to add two integers, we must define both ‘integers’ as well as the ‘add’ operation\n","3. **Produce a result**: An algorithm must produce a result, otherwise it is useless. The result can be data returned to the calling algorithm, or some other effect (for example, printing).\n","4. **Terminate in a finite time**: An algorithm must terminate (halt). If it does not (that is, it has an infinite loop), we have not created an algorithm. \n"]},{"cell_type":"markdown","metadata":{"id":"_6VGENxtJz2u"},"source":["## Basic algorithms"]},{"cell_type":"markdown","metadata":{"id":"DtkATg-2J40-"},"source":["Several algorithms are used in computer science so prevalently that they are considered ‘basic'."]},{"cell_type":"markdown","metadata":{"id":"KTPLWiUhKIIm"},"source":["#### Summation"]},{"cell_type":"markdown","metadata":{"id":"DsSu5c2SKNBW"},"source":["One commonly used algorithm in computer science is summation of a list of integers. The solution is simple: we use the add operator in a loop"]},{"cell_type":"markdown","metadata":{"id":"7-LiRRiXPMxS"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"M1xcYhF7Jfhe"},"source":["> #### Example 4: Calculate the summation of the integers in the input list, return `None` if it is an empty list"]},{"cell_type":"code","execution_count":11,"metadata":{"id":"N848EkIJeFuW"},"outputs":[],"source":["def summation(numbers):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," numbers: list\n"," The input list.\n"," Returns\n"," -------\n"," sum : int\n"," The summation of the input list, if the input is empty please return None\n"," \"\"\"\n"," # Your code here\n"," # Special case: If the numbers list is empty, return None\n"," if len(numbers) == 0:\n"," return None\n","\n"," # Start the total at 0:\n"," sum = 0\n","\n"," # Loop over each number in numbers:\n"," for current in numbers:\n"," # Add the number to the total:\n"," sum = sum + current\n","\n"," return sum"]},{"cell_type":"code","execution_count":12,"metadata":{"id":"6m7DrL1CKuTC"},"outputs":[],"source":["assert summation([1, 2, 3]) == sum([1, 2, 3])\n","assert summation([12, 20, 37]) == sum([12, 20, 37])\n","assert summation([]) == None"]},{"cell_type":"markdown","metadata":{"id":"rv3n8mkOK_Jk"},"source":["#### Product"]},{"cell_type":"markdown","metadata":{"id":"fDI8FnGNLP5v"},"source":["Another common algorithm is finding the product of a list of integers. "]},{"cell_type":"markdown","metadata":{"id":"yLq3VHUlPXcB"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"HHsf-LccJp7n"},"source":["> #### Exercise 2: Calculate the product of the integers in the input list, return `None` if it is an empty list"]},{"cell_type":"code","execution_count":13,"metadata":{"id":"dRMXgi52K9PC"},"outputs":[],"source":["def product(numbers):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," numbers: list\n"," The input list.\n"," Returns\n"," -------\n"," product : int\n"," The product of the input list, if the input is empty please return None\n"," \"\"\"\n"," # Special case: If the numbers list is empty, return None:\n"," if len(numbers) == 0:\n"," return None\n","\n"," # Your code here\n"," product = 1\n","\n"," # Loop over each number in numbers:\n"," for current in numbers:\n"," # Multiply the number to the total:\n"," product *= current\n","\n"," return product"]},{"cell_type":"code","execution_count":14,"metadata":{"id":"SjEGIheALrpT"},"outputs":[],"source":["# For Python 3.8 or later\n","assert product([1, 2, 3]) == math.prod([1, 2, 3])\n","assert product([12, 20, 37]) == math.prod([12, 20, 37])\n","assert product([]) == None"]},{"cell_type":"code","execution_count":15,"metadata":{"id":"rCASiYLvMBgB"},"outputs":[],"source":["# For Python 3.7 or earlier\n","import numpy as np\n","assert product([1, 2, 3]) == np.prod([1, 2, 3])\n","assert product([12, 20, 37]) == np.prod([12, 20, 37])\n","assert product([]) == None"]},{"cell_type":"markdown","metadata":{"id":"ikKg-haBPm6Z"},"source":["#### Smallest and largest"]},{"cell_type":"markdown","metadata":{"id":"TMZRbdhAPwtR"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"b2VrTc2rP4sA"},"source":["### Sorting"]},{"cell_type":"markdown","metadata":{"id":"p4myWDaaQCKG"},"source":["One of the most common applications in computer science is sorting, which is the process by which data is arranged according to its values. People are surrounded by data. If the data was not ordered, it would take hours and hours to find a single piece of information. Imagine the difficulty of finding someone’s telephone number in a telephone book that is not ordered!"]},{"cell_type":"markdown","metadata":{"id":"kInpY-puQOcp"},"source":["#### Selection sorts"]},{"cell_type":"markdown","metadata":{"id":"Cim4JIrGQUY5"},"source":["In a selection sort, the list to be sorted is divided into two sublists — sorted and unsorted— which are separated by an imaginary wall. We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted sublist. After each selection and swap, the imaginary wall between the two sublists moves one element \n","ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. Each time we move one element from the unsorted sublist to the sorted sublist, we have completed a sort pass. \n","\n","A list of `n` elements requires `n − 1` passes to completely \n","rearrange the data. "]},{"cell_type":"markdown","metadata":{"id":"TEV_Yd-4RbT6"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"kZ0LuE-hT1IP"},"source":["The visualization is as follows:"]},{"cell_type":"markdown","metadata":{"id":"DQvKVc1jTrJG"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"w2auVoDcYoIC"},"source":["The figure shows how the wall between the sorted and unsorted sublists moves in each pass. As we study the figure, we will see that the list is sorted after five passes, which is one less than the number of elements in the list. **Thus, if we use a loop to control the sorting, the loop will have one less iteration than the number of elements to be sorted.**"]},{"cell_type":"markdown","metadata":{"id":"1sJP0kRjS3v3"},"source":["
\n","
source: https://github.com/hustcc/JS-Sorting-Algorithm
\n","\n"]},{"cell_type":"markdown","metadata":{"id":"6D3NaAgjTHQu"},"source":["Refer to https://visualgo.net/en/sorting "]},{"cell_type":"markdown","metadata":{"id":"ee9Aspd_T-Wu"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"kQbC09knY0oh"},"source":["The algorithm uses two loops, one inside the other. The outer loop is iterated for each pass: the inner loop finds the smallest element in the unsorted list."]},{"cell_type":"markdown","metadata":{"id":"JIKDdffkU901"},"source":["> #### Example 5: Write a selection sort for list of intergers that sorts the integer from smallest to largest"]},{"cell_type":"code","execution_count":16,"metadata":{"id":"wU3rjgpRMHTq"},"outputs":[],"source":["def selection_sort(arr):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," arr: list\n"," The unsorted input list that contains integers\n"," Returns\n"," -------\n"," arr : list\n"," The sorted list\n"," \"\"\"\n"," # Your code here\n"," n = len(arr)\n"," ## Move the wall one element to the right\n"," for wall in range(n-1):\n"," ## Place the wall at the leftmost of the list (index)\n"," smallest = wall\n"," ## Find smallest element in the unsorted list\n"," for cur in range(smallest+1,n):\n"," if arr[cur] < arr[smallest]:\n"," smallest = cur\n"," ## Swap smallest element with first element in the unsorted list\n"," arr[wall], arr[smallest] = arr[smallest], arr[wall]\n"," return arr"]},{"cell_type":"code","execution_count":17,"metadata":{"id":"fqn0DzFfXxrl"},"outputs":[],"source":["assert(selection_sort([89,78,61,53,23,21,17,12,9,7,6,2,1])==sorted([89,78,61,53,23,21,17,12,9,7,6,2,1]))\n","assert(selection_sort([1,5,8,9])==sorted([1,5,8,9]))\n","assert(selection_sort([78,12,15,8,61,53,23,27])==sorted([78,12,15,8,61,53,23,27]))\n","assert(selection_sort([5])==sorted([5]))"]},{"cell_type":"markdown","metadata":{"id":"LSbMSeYoZLcq"},"source":["#### Bubble sort"]},{"cell_type":"markdown","metadata":{"id":"HlIC5BLFZRip"},"source":["In the bubble sort method, the list to be sorted is also divided into two sublists—sorted and unsorted. The smallest element is bubbled up from the unsorted sublist and moved to the sorted sublist. After the smallest element has been moved to the sorted list, the wall moves one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. \n","\n","Each time an element moves from the unsorted sublist to the sorted sublist, one sort pass is completed. Given a list of `n` elements, bubble \n","sort requires up to `n − 1` passes to sort the data."]},{"cell_type":"markdown","metadata":{"id":"PZoi3QSko6yd"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"MMTBXQ5QPi3N"},"source":["The following shows how the wall moves one element in each pass. Looking at the first pass, we start with 56 and compare it to 32. Since 56 is not less than 32, it is not moved, and we step down one element. No exchanges take place until we compare 45 to 8. Since 8 is less than 45, the two elements are exchanged, and we step down one element. Because 8 was moved down, it is now compared to 78, and these two elements are exchanged. Finally, 8 is compared to 23 and exchanged. This series of exchanges places 8 in the first \n","location, and the wall is moved up one position. **The algorithm gets its name from the way in which numbers — in this example, 8 — appear to move to the start, or top, of the list in the same way that bubbles rise through water.**"]},{"cell_type":"markdown","metadata":{"id":"FwHiE7NXpJFs"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"BrHqpd5ypWzs"},"source":["
\n","
source: https://github.com/hustcc/JS-Sorting-Algorithm
"]},{"cell_type":"markdown","metadata":{"id":"dWNtsvsDYeoe"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"YpLWDCNdQE1k"},"source":["> #### Exercise 3: Write a bubble sort for list of intergers that sorts the integer from smallest to largest"]},{"cell_type":"code","execution_count":18,"metadata":{"id":"zU4meI-1pIkK"},"outputs":[],"source":["def bubble_sort(arr):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," arr: list\n"," The unsorted input list that contains integers\n"," Returns\n"," -------\n"," arr : list\n"," The sorted list\n"," \"\"\"\n"," n = len(arr)\n"," ## Move the wall one element to the right\n"," for wall in range(n-1):\n"," ## bubble each element up to the left\n"," for j in range(n-1, wall, -1):\n"," if arr[j] < arr[j-1]:\n"," arr[j], arr[j-1] = arr[j-1], arr[j]\n"," return arr"]},{"cell_type":"code","execution_count":19,"metadata":{"id":"ecMEvcjaa3_k"},"outputs":[],"source":["assert(bubble_sort([89,78,61,53,23,21,17,12,9,7,6,2,1])==sorted([89,78,61,53,23,21,17,12,9,7,6,2,1]))\n","assert(bubble_sort([1,5,8,9])==sorted([1,5,8,9]))\n","assert(bubble_sort([78,12,15,8,61,53,23,27])==sorted([78,12,15,8,61,53,23,27]))\n","assert(bubble_sort([5])==sorted([5]))"]},{"cell_type":"code","execution_count":20,"metadata":{},"outputs":[{"data":{"text/plain":["[8, 12, 15, 23, 27, 53, 61, 78]"]},"execution_count":20,"metadata":{},"output_type":"execute_result"}],"source":["bubble_sort([78,12,15,8,61,53,23,27])"]},{"cell_type":"markdown","metadata":{"id":"68RLdysFpy1X"},"source":["#### Insertion sort"]},{"cell_type":"markdown","metadata":{"id":"7PPcfrCIpy1Y"},"source":["The insertion sort algorithm is one of the most common sorting techniques, and it is often used by card players. Each card a player picks up is inserted into the proper place in their hand of cards to maintain a particular sequence. (Card sorting is an example of a sort that uses two criteria for sorting: suit and rank.) \n","\n","In an insertion sort, as in the other two sorting algorithms discussed above, the list is divided into two parts—sorted and unsorted. In each pass, the first element of the unsorted sublist is transferred to the sorted sublist and inserted at the appropriate place. Note that a list of `n` elements will take `n − 1` passes to sort the data. "]},{"cell_type":"markdown","metadata":{"id":"xCH04LGDpy1Y"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"1vHEcVNRpy1Y"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"ctg08FeNnGuK"},"source":["As you can perceive from the above figure, the wall moves with each pass as an element is removed from the unsorted sublist and inserted into the sorted sublist. "]},{"cell_type":"markdown","metadata":{"id":"4nvYUHK7py1Y"},"source":["
\n","
source: https://github.com/hustcc/JS-Sorting-Algorithm
"]},{"cell_type":"markdown","metadata":{"id":"ILkB12Fu1HXW"},"source":["The design of insertion sort follows the same pattern seen in both selection sort and bubble sort. The outer loop is iterated for each pass, and the inner loop finds the position of insertion."]},{"cell_type":"markdown","metadata":{"id":"KUCHRcDPoz1w"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"JgfGPpg3oPjY"},"source":["> #### Exercise 4: Write an insertion sort for list of intergers that sorts the integer from smallest to largest"]},{"cell_type":"code","execution_count":1,"metadata":{"id":"Bc1iwhx-oPI5"},"outputs":[],"source":["def insertion_sort(arr):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," arr: list\n"," The unsorted input list that contains integers\n"," Returns\n"," -------\n"," arr : list\n"," The sorted list\n"," \"\"\"\n"," # Your code here\n"," n = len(arr)\n"," ## Move the wall one element to the right\n"," for wall in range(1,n):\n"," temp = arr[wall]\n"," cur = wall -1\n"," ## Find the position that we can inserted into\n"," while arr[cur] > temp and cur >= 0:\n"," arr[cur+1] = arr[cur]\n"," cur = cur -1 \n"," ## Insert the element here\n"," arr[cur+1] = temp\n"," return arr"]},{"cell_type":"code","execution_count":2,"metadata":{"id":"_fIbpsk6085q"},"outputs":[],"source":["assert(insertion_sort([89,78,61,53,23,21,17,12,9,7,6,2,1])==sorted([89,78,61,53,23,21,17,12,9,7,6,2,1]))\n","assert(insertion_sort([1,5,8,9])==sorted([1,5,8,9]))\n","assert(insertion_sort([78,12,15,8,61,53,23,27])==sorted([78,12,15,8,61,53,23,27]))\n","assert(insertion_sort([5])==sorted([5]))"]},{"cell_type":"code","execution_count":3,"metadata":{},"outputs":[{"data":{"text/plain":["[8, 12, 15, 23, 27, 53, 61, 78]"]},"execution_count":3,"metadata":{},"output_type":"execute_result"}],"source":["insertion_sort([78,12,15,8,61,53,23,27])"]},{"cell_type":"markdown","metadata":{"id":"j8nhf0oe1hMG"},"source":["The three sorting algorithms discussed here are the least efficient sorting algorithms, and should not be used if the list to be sorted has more than a few hundred elements. There are however several reasons for discussing these sorting algorithms in an introductory book:\n","\n","1. They are the simplest algorithms to understand and analyze. \n","2. They are the foundation of more efficient algorithms such as quicksort, heap sort, Shell sort, bucket sort, merge sort, radix sort, and so on. \n","\n","Most such advanced sorting algorithms are discussed in books on data structures. You may ask why there are so many sorting algorithms. The reason lies in the type of data that needs to be sorted. One algorithm may be more efficient for a list that is partially sorted, whereas another algorithm may be more efficient for a list that is completely unsorted. \n","\n","See https://www.sortvisualizer.com/ for more details"]},{"cell_type":"markdown","metadata":{"id":"SH6obA1TqW-D"},"source":["### Searching"]},{"cell_type":"markdown","metadata":{"id":"h0IlYTiH2cDf"},"source":["Another common algorithm in computer science is searching, which is the process of finding the location of a target among a list of objects. In the case of a list, searching means that given a value, we want to find the location of the first element in the list that contains that value. There are two basic searches for lists: sequential search and binary search. Sequential search can be used to locate an item in any list, **whereas binary search requires \n","the list first to be sorted.**"]},{"cell_type":"markdown","metadata":{"id":"N21lq-2eqobz"},"source":["#### Sequential search"]},{"cell_type":"markdown","metadata":{"id":"TULQtonO2tat"},"source":["Sequential search is used if the list to be searched is not ordered. Generally, we use this technique only for small lists, or lists that are not searched often. In other cases, the best approach is to first sort the list and then search it using the binary search discussed later."]},{"cell_type":"markdown","metadata":{"id":"Xcq-tYgu2zJF"},"source":["In a sequential search, we start searching for the target from the beginning of the list. We continue until we either find the target or reach the end of the list. The following figure traces the steps to find the value 62. The search algorithm needs to be designed so that the search stops when we find the target or when we reach the end of the list. "]},{"cell_type":"markdown","metadata":{"id":"jYLs4l6lqrPi"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"3GlDo91g7S_Z"},"source":["> #### Example 6: Write a sequential search for a list of intergers that return the index of the target value. Note that we should return `None` if the target does not in the list!"]},{"cell_type":"code","execution_count":21,"metadata":{"id":"gM0YaE9k3V3U"},"outputs":[],"source":["def sequential_search(arr, target):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," arr: list\n"," The unsorted input list that contains integers\n"," target: int\n"," The target we are trying to search\n"," Returns\n"," -------\n"," location : int\n"," The location or index of the target. Return None if it does not contain the target \n"," \"\"\"\n"," location = 0\n"," while location < len(arr) and arr[location] != target:\n"," location += 1\n","\n"," if location == len(arr):\n"," return None\n"," return location"]},{"cell_type":"code","execution_count":22,"metadata":{"id":"WyhcQbir5GYz"},"outputs":[],"source":["assert(sequential_search([0,5,7,10,15], 0)==[0,5,7,10,15].index(0))\n","assert(sequential_search([0,3,10,15,7], 15)==[0,3,10,15,7].index(15))\n","assert(sequential_search([0,3,10,15,7], 7)==[0,3,10,15,7].index(7))\n","assert(sequential_search([0,3,10,15,7], 6)==None)"]},{"cell_type":"markdown","metadata":{"id":"r97R_gFsqzwy"},"source":["#### Binary search"]},{"cell_type":"markdown","metadata":{"id":"JiOy0WDh6R_6"},"source":["The sequential search algorithm is very slow. If we have a list of a million elements, we must do a million comparisons in the worst case. If the list is not sorted, this is the only solution. If the list is sorted, however, we can use a more efficient algorithm called binary search. Generally speaking, programmers use a binary search when a list is large. "]},{"cell_type":"markdown","metadata":{"id":"UYzeuTe-6bFs"},"source":["A binary search starts by testing the data in the element at the middle of the list. This determines whether the target is in the first half or the second half of the list. If it is in the first half, there is no need to further check the second half. If it is in the second half, there is no need to further check the first half. **In other words, we eliminate half the list from further consideration.**"]},{"cell_type":"markdown","metadata":{"id":"pYeadXXd6lhS"},"source":["We repeat this process until we either find the target or satisfy ourselves that it is not in the list. The following figure shows how to find the target, 22, in a list of 12 numbers using three references: `first`, `mid`, and `last`. \n","\n","1. At the beginning, `first` shows 1 and `last` shows 12. Let `mid` show the middle position, (1 + 12)/ 2, or 6 if truncated to an integer. Now compare the target (22) with data at position 6 (21). The target is greater than this value, so we ignore the first half of the list.\n","\n","2. Move `first` after `mid`, to position 7. Let `mid` show the middle of the second half, (7  +  12) / 2, or 9. Now compare the target (22) with data at position 9 (62). The target is smaller than this value, so we ignore the integers from this value (62) to the end.\n","\n","3. Move `last` before `mid` to position 8. Recalculate mid again, (8 + 7) / 2, or 7. Compare the target (22) with the value at this position (22). We have found the target and can quit. "]},{"cell_type":"markdown","metadata":{"id":"3Ul2L49-q2J6"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"ZFZ83auO7IKR"},"source":["The algorithm for binary search needs to be designed to find the target or to stop if the target is not in the list. It can be shown that if the target is not found in the list, the value of last becomes smaller than the value of first, an abnormal condition that helps us to know when to come out of the loop. "]},{"cell_type":"markdown","metadata":{"id":"nzdFVoMQ9T1I"},"source":["> #### Exercise 5: Write a binary search for a sorted list of intergers that return the index of the target value. Note that we should return `None` if the target does not in the list!"]},{"cell_type":"code","execution_count":4,"metadata":{"id":"f4uftyKE7n-Y"},"outputs":[],"source":["def binary_search(arr, target):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," arr: list\n"," The sorted input list that contains integers\n"," target: int\n"," The target we are trying to search\n"," Returns\n"," -------\n"," location : int\n"," The location or index of the target. Return None if it does not contain the target \n"," \"\"\"\n"," first = 0\n"," last = len(arr) - 1\n"," while first <= last:\n"," mid = (first + last) // 2\n"," # Your code here\n"," # Move the cursor\n"," if target > arr[mid]:\n"," mid = (first + last) // 2\n"," first = mid + 1\n"," # Move the cursor\n"," elif target < arr[mid]:\n"," mid = (first + last) // 2\n"," last = mid - 1\n"," # Return the index\n"," else:\n"," location = mid\n"," return location\n"," return None"]},{"cell_type":"code","execution_count":5,"metadata":{"id":"5PKxJmbJ8_MH"},"outputs":[],"source":["assert(binary_search(sorted([0,5,7,10,15]), 0)==sorted([0,5,7,10,15]).index(0))\n","assert(binary_search(sorted([0,3,10,15,7]), 15)==sorted([0,3,10,15,7]).index(15))\n","assert(binary_search(sorted([0,3,10,15,7]), 7)==sorted([0,3,10,15,7]).index(7))\n","assert(binary_search(sorted([0,3,10,15,7]), 6)==None)"]},{"cell_type":"markdown","metadata":{"id":"ztT3kM94rA4T"},"source":["## Recursion"]},{"cell_type":"markdown","metadata":{"id":"__jd3WsH9dyY"},"source":["In general, there are two approaches to writing algorithms for solving a problem. One uses iteration, the other uses recursion. Recursion is a process in which an algorithm calls itself. "]},{"cell_type":"markdown","metadata":{"id":"swDUHpwbrDTK"},"source":["### Iterative"]},{"cell_type":"markdown","metadata":{"id":"Jp0m2CcV9hjS"},"source":["To study a simple example, consider the calculation of a factorial. The factorial of a integer is the product of the integral values from 1 to the integer. The definition is iterative as shown below. An algorithm is iterative whenever the definition does not involve the algorithm itself. "]},{"cell_type":"markdown","metadata":{"id":"EmtBh04MrH3T"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"98e3bPB_rRGa"},"source":["### Recursive"]},{"cell_type":"markdown","metadata":{"id":"nvpTDlSO9rhH"},"source":["An algorithm is defined recursively whenever the algorithm appears within the definition itself. For example, the factorial function can be defined recursively as shown below. "]},{"cell_type":"markdown","metadata":{"id":"C6Oh46tjrUXD"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"ZYZDh7B49w1f"},"source":["The decomposition of `Factorial(3)`, using recursion, is shown below. If we study the figure carefully, we will note that the recursive solution for a problem involves a two-way journey. First we decompose the problem from top to bottom, and then we solve it from bottom to top.\n","\n","Although the recursive calculation looks more difficult when using paper and pencil, it is often a much easier and more elegant solution when using computers. Additionally, it offers a conceptual simplicity to the creator and the reader!"]},{"cell_type":"markdown","metadata":{"id":"OOxLuSFxragZ"},"source":["
"]},{"cell_type":"markdown","metadata":{"id":"hX-Ha5Et_Q6d"},"source":["#### Example 7: Try to write an algorithm to solve the factorial problem using recursion!"]},{"cell_type":"code","execution_count":23,"metadata":{"id":"SgXBrcgI_OsR"},"outputs":[],"source":["def Factorial_r(n):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," n: int\n"," The target factorial which is a non-negative integer\n"," Returns\n"," -------\n"," results : int\n"," The result number \n"," \"\"\"\n"," if n == 0:\n"," return 1\n"," else:\n"," return n*Factorial_r(n-1)"]},{"cell_type":"code","execution_count":24,"metadata":{"id":"MlAv54VJ_ta-"},"outputs":[],"source":["import math\n","assert(Factorial_r(5)==math.factorial(5))\n","assert(Factorial_r(10)==math.factorial(10))\n","assert(Factorial_r(1)==math.factorial(1))\n","assert(Factorial_r(0)==math.factorial(0))"]},{"cell_type":"markdown","metadata":{"id":"krbZGR4U-IBX"},"source":["#### Exercise 6: Try to write an algorithm to solve the factorial problem iteratively!"]},{"cell_type":"code","execution_count":17,"metadata":{"id":"irvEHJU6py1Y"},"outputs":[],"source":["def Factorial(n):\n"," \"\"\"\n"," Parameters\n"," ----------\n"," n: int\n"," The target factorial which is a nonnegative integer\n"," Returns\n"," -------\n"," results : int\n"," The result number \n"," \"\"\"\n"," # Your code here\n"," results = 1\n"," # Use product-like algorithm to compute it iteratively\n"," for i in range(1,n+1):\n"," results = results * i\n"," return results"]},{"cell_type":"code","execution_count":18,"metadata":{"id":"FtYvPaQJ-wFH"},"outputs":[],"source":["assert(Factorial(5)==math.factorial(5))\n","assert(Factorial(10)==math.factorial(10))\n","assert(Factorial(1)==math.factorial(1))\n","assert(Factorial(0)==math.factorial(0))"]}],"metadata":{"colab":{"provenance":[],"toc_visible":true},"kernelspec":{"display_name":"Python 3.8.8 ('base')","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.8.8"},"vscode":{"interpreter":{"hash":"ffe9a5d1be64f395cda62646beb00f4fbc1d5c319e2b42024d6d4b4beddf19a5"}}},"nbformat":4,"nbformat_minor":0}